package com.jinsp.startup_library.sort;

import com.jinsp.startup_library.Startup;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * Created by luoshuai on 2/25/22
 * <p>
 * 启动任务拓扑排序
 */
public class StartupTopologySort {

    public static StartupTopologyResultBean sort(List<Startup<?>> startupList) {
        if (startupList == null || startupList.size() == 0) {
            return null;
        }
        Queue<Startup<?>> zeroDependenceStartupQueue = new ArrayDeque<>();
        Map<Class<? extends Startup<?>>, List<Class<? extends Startup<?>>>> nextStartupMap = new HashMap<>();
        Map<Class<? extends Startup<?>>, Startup<?>> startupMap = new HashMap<>();
        Map<Startup<?>, Integer> dependenceCountMap = new HashMap<>();
        for (Startup<?> startup : startupList) {
            startupMap.put((Class<? extends Startup<?>>) startup.getClass(), startup);
            dependenceCountMap.put(startup, startup.getDependenceCount());
            if (startup.getDependenceCount() == 0) {
                zeroDependenceStartupQueue.add(startup);
            } else {
                List<Class<? extends Startup<?>>> dependenceList = startup.getDependenceList();
                for (Class<? extends Startup<?>> dependenceStartup : dependenceList) {
                    List<Class<? extends Startup<?>>> nextStartupList = nextStartupMap.get(dependenceStartup);
                    if (nextStartupList == null) {
                        nextStartupList = new ArrayList<>();
                        nextStartupMap.put(dependenceStartup, nextStartupList);
                    }
                    nextStartupList.add((Class<? extends Startup<?>>) startup.getClass());
                }
            }
        }
        List<Startup<?>> resultStartupList = new ArrayList<>();
        List<Startup<?>> mainThreadStartupList = new ArrayList<>(); //主线程启动任务
        List<Startup<?>> threadStartupList = new ArrayList<>();     //子线程启动任务
        //遍历零入度表
        while (!zeroDependenceStartupQueue.isEmpty()) {
            Startup<?> startup = zeroDependenceStartupQueue.poll();
            if (startup.isOnMainThread()) {
                mainThreadStartupList.add(startup);
            } else {
                threadStartupList.add(startup);
            }
            List<Class<? extends Startup<?>>> nextStartupList = nextStartupMap.get(startup.getClass());
            if (nextStartupList != null) {
                for (Class<? extends Startup<?>> startupClass : nextStartupList) {
                    Startup<?> nextStartup = startupMap.get(startupClass);
                    int nextStartupDependenceCount = dependenceCountMap.get(nextStartup);
                    dependenceCountMap.put(nextStartup, --nextStartupDependenceCount);
                    if (nextStartupDependenceCount == 0) {
                        zeroDependenceStartupQueue.offer(nextStartup);
                    }
                }
            }
        }
        resultStartupList.addAll(threadStartupList);
        resultStartupList.addAll(mainThreadStartupList);
        return new StartupTopologyResultBean(nextStartupMap, startupMap, resultStartupList);
    }
}
